The present invention relates to a method for determining a path, which may be a centerline path, along a biological object having a lumen that is included in a three-dimensional volume data set representing a biological object.
Patient imaging methods such as computer-assisted tomography (CT), magnetic resonance imaging (MRI), ultrasound and positron-emission tomography (PET) generate large three-dimensional volume data sets representing all or part of a patient's body. These volume data sets are highly detailed and allow complex studies of the body to be made. Advanced image processing techniques enhance the utility of the visualization of these data sets. For example, a physician may use a three-dimensional data set of an artery to determine the extent of stenosis or to plan the stenting of an aneurysm. This requires accurate identification of the centerline path along the lumen and measurements associated with the anatomy and physiology. Other applications may also require a path to be identified, including direct medical applications such as determining the exact location of a tumor or polyp to be operated on in an organ such as the colon or lungs, or medical imaging techniques such as virtual endoscopy and curved multi-planar reformatting (MPR).
A number of methods have been proposed for calculating such paths. Important criteria include speed and simplicity of computation, and keeping the path away from the object wall or from straying out of the object altogether. It is not generally trivial to satisfy all these criteria, and the previously proposed methods are many and varied. The methods include those based on mathematical techniques designed for vessel wall avoidance [1, 2, 3]; and those based on mathematical techniques that use erosion to determine a central line or medial axis along the vessel [4, 5], or that use 3D topological thinning to find the centerline [6]. Other techniques include labeling points in the data set with their distance from the end of the path using a wavefront technique to avoid obstacles and calculating the path by moving from point to point according to the closest distance to the end point [7]; convolution filtering to approximate a central track [8]; defining a cube around the region of interest and using the intersections of a region grown out from the current camera position with the cube to calculate centerlines from the camera to the intersections and selecting the best centerline [9]; and obtaining an initial path by using a distance label map to connect start and end voxels via intermediate voxels according to their distance from the start and end voxels, and centering the path using spheres [10].
Some methods make use of Dijkstra's algorithm. This is an algorithm that finds the minimum path length (or shortest path) between two points or nodes in a network made up of a plurality of nodes, some or all pairs of which are connected by a path or branch, the branches having known lengths [11]. A three-dimensional volume data set is made up of an array of voxels arranged regularly in three dimensions, each voxel having a value related to a physical attribute of the material represented by that voxel. The distances between the voxels are known, so Dijkstra's algorithm can be applied by considering each voxel to be a node in a network, the nodes connected to the adjacent nodes.
For lumen path finding, it is important that the path stays within the lumen from the start to the end of the path. A path that does this is not necessarily the shortest path through the data set between the start and end points, so Dijkstra's algorithm needs to be constrained to find a path within the lumen. Kanitsar [12, 13] proposes to do this for a network of blood vessels by replacing the branch length by a cost function for each pair of voxels. The cost function is the distance between the two voxels weighted by factors that give a low cost to paths lying within the vessel and a high cost to paths partially or wholly outside the vessel. The algorithm then seeks the path with the lowest cost rather than the shortest distance.
A start point for the path is selected, and Dijkstra's algorithm calculates the minimum cost path from the start point to all points in the data set. In practice the algorithm can stop when the minimum cost path to a desired end point is found. The algorithm operates by computing the paths from the start point to other nodes (voxels) in an expanding frontier “shell”. The shell expands in contours of approximately equal cost, with minimum cost paths then available between the start point and any point inside the shell. An advantage of this approach is that once a path from the start point to a first end point has been found, a further path from the start point to a second end point can be delivered quickly, even at interactive speed. If the second end point is already in the computed shell, the optimal path to that point can be provided immediately; if it is not, the calculation can be continued re-using existing results and expanding the shell further until it reaches the second end point. This computational re-usage can be valuable.
However, a disadvantage of Dijkstra's algorithm is that the computation overall can be very slow. The algorithm does not make direct use of the desired end point of the path so to reach the end point it must expand the shell of known paths in all directions, even those leading in the opposite direction to the end point. In the context of lumen path finding for applications such as stent planning and stenosis sizing, this is a serious problem that can result in execution times of several tens of seconds in many cases, which users tend to find unacceptably slow.